package com.zs.letcode.search;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

/**
 * 存在重复元素 III
 * 给你一个整数数组 nums 和两个整数k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
 * <p>
 * 如果存在则返回 true，不存在返回 false。
 * <p>
 * 
 * <p>
 * 示例1：
 * <p>
 * 输入：nums = [1,2,3,1], k = 3, t = 0
 * 输出：true
 * 示例 2：
 * <p>
 * 输入：nums = [1,0,1,1], k = 1, t = 2
 * 输出：true
 * 示例 3：
 * <p>
 * 输入：nums = [1,5,9,1,5,9], k = 2, t = 3
 * 输出：false
 * 
 * <p>
 * 提示：
 * <p>
 * 0 <= nums.length <= 2 * 104
 * -231 <= nums[i] <= 231 - 1
 * 0 <= k <= 104
 * 0 <= t <= 231 - 1
 * 相关标签
 * 数组
 * 桶排序
 * 有序集合
 * 排序
 * 滑动窗口
 * <p>
 * Python3
 * <p>
 * <p>
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/all-about-lockup-table/xhw24c/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/6/26 11:23
 */
public class Chapter16 {
    public static void main(String[] args) {

    }

    private static class Solution {
        /**
         * 方法一：滑动窗口 + 有序集合
         */
        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            int n = nums.length;
            TreeSet<Long> set = new TreeSet<>();
            for (int i = 0; i < n; i++) {
                Long ceiling = set.ceiling((long) nums[i] - (long) t);
                if (ceiling != null && ceiling <= (long) nums[i] + (long) t) {
                    return true;
                }
                set.add((long) nums[i]);
                if (i >= k) {
                    set.remove((long) nums[i - k]);
                }
            }
            return false;
        }

        /**
         * 方法二：桶
         */
        public boolean containsNearbyAlmostDuplicate1(int[] nums, int k, int t) {
            int n = nums.length;
            Map<Long, Long> map = new HashMap<>();
            long w = (long) t + 1;
            for (int i = 0; i < n; i++) {
                long id = getID(nums[i], w);
                if (map.containsKey(id)) {
                    return true;
                }
                if (map.containsKey(id + 1) && Math.abs(nums[i] - map.get(id + 1)) < w) {
                    return true;
                }
                map.put(id, (long) nums[i]);
                if (i > k) {
                    map.remove(getID(nums[i - k], w));
                }
            }
            return false;
        }

        private long getID(int x, long w) {
            if (x >= 0) {
                return x / w;
            }
            return (x + 1) / w - 1;
        }
    }
}
